{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #序列重建"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sequenceReconstruction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #序列重建"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的整数数组 <code>nums</code> ，其中 <code>nums</code> 是范围为 <code>[1，n]</code> 的整数的排列。还提供了一个 2D 整数数组&nbsp;<code>sequences</code>&nbsp;，其中&nbsp;<code>sequences[i]</code>&nbsp;是&nbsp;<code>nums</code>&nbsp;的子序列。<br />\n",
    "检查 <code>nums</code> 是否是唯一的最短&nbsp;<strong>超序列</strong> 。最短 <strong>超序列</strong> 是 <strong>长度最短</strong> 的序列，并且所有序列&nbsp;<code>sequences[i]</code>&nbsp;都是它的子序列。对于给定的数组&nbsp;<code>sequences</code>&nbsp;，可能存在多个有效的 <strong>超序列</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，对于&nbsp;<code>sequences = [[1,2],[1,3]]</code>&nbsp;，有两个最短的 <strong>超序列</strong> ，<code>[1,2,3]</code> 和 <code>[1,3,2]</code> 。</li>\n",
    "\t<li>而对于&nbsp;<code>sequences = [[1,2],[1,3],[1,2,3]]</code>&nbsp;，唯一可能的最短 <strong>超序列</strong> 是 <code>[1,2,3]</code> 。<code>[1,2,3,4]</code> 是可能的超序列，但不是最短的。</li>\n",
    "</ul>\n",
    "\n",
    "<p><em>如果 <code>nums</code> 是序列的唯一最短 <strong>超序列</strong> ，则返回 <code>true</code> ，否则返回 <code>false</code> 。</em><br />\n",
    "<strong>子序列</strong> 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], sequences = [[1,2],[1,3]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>有两种可能的超序列：[1,2,3]和[1,3,2]。\n",
    "序列 [1,2] 是[<u><strong>1,2</strong></u>,3]和[<u><strong>1</strong></u>,3,<u><strong>2</strong></u>]的子序列。\n",
    "序列 [1,3] 是[<u><strong>1</strong></u>,2,<u><strong>3</strong></u>]和[<u><strong>1,3</strong></u>,2]的子序列。\n",
    "因为 nums 不是唯一最短的超序列，所以返回false。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], sequences = [[1,2]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>最短可能的超序列为 [1,2]。\n",
    "序列 [1,2] 是它的子序列：[<u><strong>1,2</strong></u>]。\n",
    "因为 nums 不是最短的超序列，所以返回false。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>最短可能的超序列为[1,2,3]。\n",
    "序列 [1,2] 是它的一个子序列：[<strong>1,2</strong>,3]。\n",
    "序列 [1,3] 是它的一个子序列：[<u><strong>1</strong></u>,2,<u><strong>3</strong></u>]。\n",
    "序列 [2,3] 是它的一个子序列：[1,<u><strong>2,3</strong></u>]。\n",
    "因为 nums 是唯一最短的超序列，所以返回true。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;是&nbsp;<code>[1, n]</code>&nbsp;范围内所有整数的排列</li>\n",
    "\t<li><code>1 &lt;= sequences.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= sequences[i].length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= sum(sequences[i].length) &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= sequences[i][j] &lt;= n</code></li>\n",
    "\t<li><code>sequences</code>&nbsp;的所有数组都是 <strong>唯一 </strong>的</li>\n",
    "\t<li><code>sequences[i]</code>&nbsp;是&nbsp;<code>nums</code> 的一个子序列</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 444&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/sequence-reconstruction/\">https://leetcode-cn.com/problems/sequence-reconstruction/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ur2n8P](https://leetcode.cn/problems/ur2n8P/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ur2n8P](https://leetcode.cn/problems/ur2n8P/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n[[1,2],[1,3]]', '[1,2,3]\\n[[1,2]]', '[1,2,3]\\n[[1,2],[1,3],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # 这里首先要假设 sequences 一定存在超序列，且 nums 中不存在重复数字，否则这道题就不能用“检验法”\n",
    "        # 以下是检验法的基本逻辑：\n",
    "        # 1. 如果 nums 中的所有数对的偏序关系都能在 sequences 中找到，那么一定是最短的超序列。因为，如果不是最短的超序列，那么一定存在冗余——即某个相邻数对，其偏序不出现在 sequences 中\n",
    "        # 2. 如果 nums 中的所有数对的偏序关系都能在 sequences 中找到，那么一定是唯一的最短超序列，否则，假设存在其他一样短的超序列，那么就意味着 nums 中某些相邻数对的偏序关系不再存在，而 nums 既然是超序列，这些偏序关系肯定是不能被忽略的，因此矛盾。\n",
    "        m = {nums[i]: nums[i+1] for i in range(len(nums)-1)}\n",
    "        for s in sequences:\n",
    "            for i in range(len(s)-1):\n",
    "                if s[i+1] == m.get(s[i]):\n",
    "                    del m[s[i]]\n",
    "        return len(m) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        edge = [[] for _ in range(n+1)]\n",
    "        for s in sequences:\n",
    "            for x,y in pairwise(s):\n",
    "                edge[x].append(y)\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            cur = nums[i]\n",
    "            if nums[i+1] not in edge[cur]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # 首先证明：如果nums是唯一最短超序列,\n",
    "        # 那么对于任意[nums[i-1],nums[i]],必然存在sequencs[i] = [...,a,b,...]\n",
    "       \n",
    "        # 反证法证明如下 \n",
    "        # 设 nums[i] = a , nums[i+1] = b,且sequences[i]中不存在[...,a,b,...]\n",
    "\n",
    "        # 1. sequence[i]中存在 [...,a,c,...,b...]\n",
    "        # 那么c必须在a，b之间，当前的nums不可能成立\n",
    "\n",
    "        # 2. 任意sequence[i]中都不存在[...a,...,b....]\n",
    "        # 那么b可以放在a前面,nums[i]和nums[i+1]可以互换，nums不再唯一\n",
    "\n",
    "        # 综上可知nums[i]= a,nums[i+1],那么sequence[i]中一定存在[a,b]\n",
    "\n",
    "        pair_list =list()\n",
    "        for seq in sequences:\n",
    "            for i in range(1,len(seq)):\n",
    "                pair_list.append([seq[i-1],seq[i]])\n",
    "        for i in range(1,len(nums)):\n",
    "            if [nums[i-1],nums[i]] not in pair_list:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        return len(edges := {(a, b) for seq in sequences for a,b in pairwise(seq)}) >= 0 and all((a, b) in edges for a, b in pairwise(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        edges = [[] for i in range(n+1)]\n",
    "        for s in sequences:\n",
    "            for x, y in pairwise(s):\n",
    "                edges[x].append(y)\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            cur = nums[i]\n",
    "            if nums[i+1] not in edges[cur]:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        deg = [0] * (n + 1)\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                g[seq[i]].append(seq[i + 1])\n",
    "                deg[seq[i + 1]] += 1\n",
    "        deg0_set = set()\n",
    "        for i in range(1, n + 1):\n",
    "            if deg[i] == 0:\n",
    "                deg0_set.add(i)\n",
    "        for i in range(n):\n",
    "            if len(deg0_set) != 1:\n",
    "                return False\n",
    "            if nums[i] not in deg0_set:\n",
    "                return False\n",
    "            deg0_set.clear()\n",
    "            for j in g[nums[i]]:\n",
    "                deg[j] -= 1\n",
    "                if deg[j] == 0:\n",
    "                    deg0_set.add(j)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        edges = [[] for i in range(n+1)]\n",
    "        for s in sequences:\n",
    "            for x, y in pairwise(s):\n",
    "                edges[x].append(y)\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            cur = nums[i]\n",
    "            if nums[i+1] not in edges[cur]:\n",
    "                return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        return len(edges := {(a, b) for seq in sequences for a,b in pairwise(seq)}) >= 0 and all((a, b) in edges for a, b in pairwise(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        s = set()\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)-1):\n",
    "                s.add((seq[i],seq[i+1]))\n",
    "        \n",
    "        for i in range(len(nums)-1):\n",
    "            if (nums[i], nums[i+1]) not in s:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        d = [0] * n\n",
    "        for l in sequences:\n",
    "            for x,y in pairwise(l):\n",
    "                if y-1 in g[x-1]: continue\n",
    "                g[x-1].append(y-1)\n",
    "                d[y-1] += 1\n",
    "        q = list(filter(lambda i:d[i]==0, range(n)))\n",
    "        for x in nums:\n",
    "            x -= 1\n",
    "            if len(q) != 1 or q[0] != x: return False\n",
    "            q.pop()\n",
    "            for y in g[x]:\n",
    "                d[y] -= 1\n",
    "                if d[y] == 0: q.append(y)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = [[] for _ in range(len(nums)+1)]\n",
    "        indegree = [0] * (len(nums)+1)\n",
    "        for pre in sequences:\n",
    "            for i in range(1, len(pre)):\n",
    "                if pre[i] not in graph[pre[i-1]]:\n",
    "                    graph[pre[i-1]].append(pre[i])\n",
    "                indegree[pre[i]] += 1\n",
    "\n",
    "        q = deque()\n",
    "        for i in range(1, len(indegree)):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            # 关键\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            cur = q.popleft()\n",
    "            for e in graph[cur]:\n",
    "                indegree[e] -= 1\n",
    "                if indegree[e] == 0:\n",
    "                    q.append(e)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        d = [0] * (n + 1)\n",
    "        for s in sequences:\n",
    "            m = len(s)\n",
    "            for i in range(1, m):\n",
    "                d[s[i]] += 1\n",
    "                g[s[i - 1]].append(s[i])\n",
    "        q = []\n",
    "        res = []\n",
    "        for i in range(1, n + 1):\n",
    "            if d[i] == 0:\n",
    "                q.append(i)\n",
    "                res.append(i)\n",
    "        if len(res) > 1:\n",
    "            return False\n",
    "        while q:\n",
    "            t = q.pop(0)\n",
    "            for v in g[t]:\n",
    "                d[v] -= 1\n",
    "                if d[v] == 0:\n",
    "                    q.append(v)\n",
    "                    res.append(v)\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "        if len(res) != n:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if res[i] != nums[i]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool: \n",
    "        # 思路：拓扑排序（从 outDegree 找出一条等于 nums 数字序列的路径）\n",
    "        # outDegree -> 出度表\n",
    "        outDegree = {node:{} for node in nums}                \n",
    "\n",
    "        # 通过 sequences 建立出度表\n",
    "        for sequence in sequences:  \n",
    "            # 如果 sequence 中的数字不在 nums 列表中\n",
    "            # 比如：nums=[1]，sequences=[[2]]\n",
    "            for num in sequence:\n",
    "                if num not in outDegree:\n",
    "                    return False\n",
    "\n",
    "            for i in range(len(sequence)-1):   \n",
    "                u, v = sequence[i], sequence[i+1]\n",
    "\n",
    "                # 判断是否有自环和环的出现  \n",
    "                # 比如：nums=[1,2,3], sequences=[[1,1],[1,2],[2,3],[3,1]]\n",
    "                if u == v or u in outDegree[v]:\n",
    "                    return False\n",
    "\n",
    "                outDegree[u][v] = True       \n",
    "        \n",
    "        # 对出度表进行验证，看看是否可以通过出度表来构建 nums 中的数字序列\n",
    "        i, flag = 0, True\n",
    "        while i < len(nums)-1:\n",
    "            u, v = nums[i], nums[i+1]           \n",
    "            if v not in outDegree[u]:            \n",
    "                flag = False\n",
    "                break\n",
    "            del outDegree[u]\n",
    "            i += 1\n",
    "\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        method = 'leetcode'\n",
    "        if method == 'leetcode':\n",
    "            n = len(nums)\n",
    "            g = [[] for _ in range(n)]\n",
    "            inDeg = [0] * n\n",
    "            for sequence in sequences:\n",
    "                for x, y in pairwise(sequence):\n",
    "                    g[x - 1].append(y - 1)\n",
    "                    inDeg[y - 1] += 1\n",
    "            q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "            while q:\n",
    "                if len(q) > 1:\n",
    "                    return False\n",
    "                x = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    inDeg[y] -= 1\n",
    "                    if inDeg[y] == 0:\n",
    "                        q.append(y)\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n=len(nums)\n",
    "        indegree=[0]*n\n",
    "        # graph=[set() for i in range(n)]\n",
    "        graph=[[] for i in range(n)]\n",
    "        for seq in sequences:\n",
    "            for x,y in pairwise(seq):\n",
    "                indegree[y-1]+=1\n",
    "                # graph[x-1].add(y-1)\n",
    "                graph[x-1].append(y-1)\n",
    "\n",
    "        q=deque([i for i,d in enumerate(indegree) if d==0])\n",
    "        while q:\n",
    "            if len(q)>1:\n",
    "                return False\n",
    "            j=q.popleft()\n",
    "            # for y in list(graph[j]):\n",
    "            for y in graph[j]:\n",
    "                indegree[y]-=1\n",
    "                if indegree[y]==0:\n",
    "                    q.append(y)\n",
    "                \n",
    "        return True\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        graph = collections.defaultdict(list)\n",
    "        degree = [0] * (n + 1)\n",
    "\n",
    "        for sequence in sequences:\n",
    "            for idx in range(len(sequence) - 1):\n",
    "                graph[sequence[idx]].append(sequence[idx + 1])\n",
    "                degree[sequence[idx + 1]] += 1\n",
    "\n",
    "        q = collections.deque()\n",
    "        for idx in range(1, n + 1):\n",
    "            if degree[idx] == 0:\n",
    "                q.append(idx)\n",
    "\n",
    "        if len(q) > 1:\n",
    "            return False\n",
    "\n",
    "        res_idx = 0\n",
    "        while len(q) > 0:\n",
    "            node = q.popleft()\n",
    "            if nums[res_idx] != node:\n",
    "                return False\n",
    "            res_idx += 1\n",
    "\n",
    "            for next_node in graph[node]:\n",
    "                degree[next_node] -= 1\n",
    "                if degree[next_node] == 0:\n",
    "                    q.append(next_node)\n",
    "\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        #跑拓扑排序\n",
    "        n=len(nums)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        degree=[0]*n\n",
    "        for li in sequences:\n",
    "            for u,v in pairwise(li):\n",
    "                graph[u-1].append(v-1)\n",
    "                degree[v-1]+=1\n",
    "        #建图完成\n",
    "        quene=[i for i in range(n) if degree[i]==0]\n",
    "        while quene:\n",
    "            if len(quene)>1:\n",
    "                return False\n",
    "            node=quene.pop(0)\n",
    "            for j in graph[node]:\n",
    "                degree[j]-=1\n",
    "                if degree[j]==0:\n",
    "                    quene.append(j)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n=len(nums)+1\n",
    "        dt=[[] for i in range(n)]\n",
    "        inD=[0]*n\n",
    "        for s in sequences:\n",
    "            for x in range(len(s)-1):\n",
    "                i=s[x]\n",
    "                j=s[x+1]\n",
    "                inD[j]+=1\n",
    "                dt[i].append(j)\n",
    "        q=[]\n",
    "        for i in range(1,n):\n",
    "            if inD[i]==0:\n",
    "                q.append(i)\n",
    "\n",
    "        while(q):\n",
    "            print(q)\n",
    "            if len(q)>1:\n",
    "                return False\n",
    "            xq=q.pop()\n",
    "            nx=dt[xq]\n",
    "            for i in nx:\n",
    "                inD[i]-=1\n",
    "                if inD[i]==0:\n",
    "                    q.append(i)\n",
    "        return True\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x - 1].append(y - 1)\n",
    "                inDeg[y - 1] += 1\n",
    "\n",
    "        q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True\n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x - 1].append(y - 1)\n",
    "                inDeg[y - 1] += 1\n",
    "\n",
    "        q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # 建图\n",
    "        G = defaultdict(list)\n",
    "        for l in sequences:\n",
    "            for i, j in pairwise(l):\n",
    "                if j not in G[i]:\n",
    "                    G[i].append(j)\n",
    "        # 判断是否有一条线贯穿始终\n",
    "        cnt = 0\n",
    "        q = deque([nums[0]])\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                x = q.popleft()\n",
    "                for y in G[x]:\n",
    "                    q.append(y)\n",
    "            cnt += 1\n",
    "        return cnt == len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        a = [[] for _ in range(n+1)]\n",
    "        count = [0 for _ in range(n+1)]\n",
    "        indexes = [0 for _ in range(n+1)]\n",
    "        for i, sequence in enumerate(sequences):\n",
    "            for x in sequence:\n",
    "                a[x].append(i)\n",
    "            count[sequence[0]] += 1\n",
    "            indexes[i] = 0\n",
    "        first = 0\n",
    "        for x in range(1, n + 1):\n",
    "            if count[x] == len(a[x]):\n",
    "                if first != 0:\n",
    "                    return False\n",
    "                first = x\n",
    "        for x in nums:\n",
    "            if x != first:\n",
    "                return False\n",
    "            first = 0\n",
    "            for i in a[x]:\n",
    "                indexes[i] += 1\n",
    "                if indexes[i] < len(sequences[i]):\n",
    "                    y = sequences[i][indexes[i]]\n",
    "                    count[y] += 1\n",
    "                    if count[y] == len(a[y]):\n",
    "                        if first != 0:\n",
    "                            return False\n",
    "                        first = y\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x - 1].append(y - 1)\n",
    "                inDeg[y - 1] += 1\n",
    "\n",
    "        q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        #跑拓扑排序\n",
    "        n=len(nums)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        degree=[0]*n\n",
    "        for li in sequences:\n",
    "            for u,v in pairwise(li):\n",
    "                graph[u-1].append(v-1)\n",
    "                degree[v-1]+=1\n",
    "        #建图完成\n",
    "        quene=[i for i in range(n) if degree[i]==0]\n",
    "        while quene:\n",
    "            if len(quene)>1:\n",
    "                return False\n",
    "            node=quene.pop(0)\n",
    "            for j in graph[node]:\n",
    "                degree[j]-=1\n",
    "                if degree[j]==0:\n",
    "                    quene.append(j)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = collections.defaultdict(list)\n",
    "        indegre = collections.defaultdict(int)\n",
    "\n",
    "        for sequence in sequences:\n",
    "            for i in range(len(sequence)-1):\n",
    "                graph[sequence[i]].append(sequence[i+1])\n",
    "                indegre[sequence[i+1]]+=1\n",
    "\n",
    "\n",
    "        queue = collections.deque()\n",
    "        for node in nums:\n",
    "            if indegre[node]==0:\n",
    "                queue.append(node)\n",
    "\n",
    "        # top_sort = []\n",
    "        # print(queue, indegre)\n",
    "        while queue:\n",
    "            len_q = len(queue)\n",
    "            if len_q>1:\n",
    "                return False\n",
    "            for i in range(len_q):\n",
    "                x = queue.popleft()\n",
    "\n",
    "                if not nums:\n",
    "                    return False\n",
    "                num = nums.pop(0)\n",
    "                if x!=num:\n",
    "                    return False\n",
    "                # top_sort.append(x)\n",
    "\n",
    "                for nei in graph[x]:\n",
    "                    indegre[nei] -= 1\n",
    "                    if indegre[nei]==0:\n",
    "                        queue.append(nei)\n",
    "\n",
    "        # print(top_sort)\n",
    "\n",
    "        return not nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        edge = defaultdict(list)\n",
    "        degree = defaultdict(int)\n",
    "        for seq in sequences:\n",
    "            m = len(seq)\n",
    "            for i in range(1,m):\n",
    "                edge[seq[i-1]].append(seq[i])\n",
    "                degree[seq[i]] += 1\n",
    "        \n",
    "        n = len(nums)\n",
    "        j = 0\n",
    "        st = [i for i in range(1,n+1) if not degree[i]]\n",
    "        while st and j < n:\n",
    "            if len(st) > 1:\n",
    "                return False\n",
    "            nex = []\n",
    "            if st[0] != nums[j]:\n",
    "                return False\n",
    "            j += 1\n",
    "            for cur in edge[st[0]]:\n",
    "                degree[cur] -= 1\n",
    "                if not degree[cur]:\n",
    "                    nex.append(cur)\n",
    "            st = nex[:]\n",
    "        return j == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "        for sequence in sequences:\n",
    "            for x, y in pairwise(sequence):\n",
    "                g[x - 1].append(y - 1)\n",
    "                inDeg[y - 1] += 1\n",
    "        \n",
    "        q = deque([i for i, d in enumerate(inDeg) if d == 0])\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        inDeg = [0] * n\n",
    "\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                g[seq[i] - 1].append(seq[i + 1] - 1)\n",
    "                inDeg[seq[i + 1] - 1] += 1\n",
    "\n",
    "        q = queue.Queue()\n",
    "        for i in range (len(inDeg)):\n",
    "            if inDeg[i] == 0:\n",
    "                q.put(i)\n",
    "                \n",
    "        while not q.empty():\n",
    "            if q.qsize() > 1:\n",
    "                return False\n",
    "            x = q.get()\n",
    "            for y in g[x]:\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.put(y)\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = collections.defaultdict(list)\n",
    "        indegre = collections.defaultdict(int)\n",
    "\n",
    "        for sequence in sequences:\n",
    "            for i in range(len(sequence)-1):\n",
    "                graph[sequence[i]].append(sequence[i+1])\n",
    "                indegre[sequence[i+1]]+=1\n",
    "\n",
    "\n",
    "        queue = collections.deque()\n",
    "        for node in nums:\n",
    "            if indegre[node]==0:\n",
    "                queue.append(node)\n",
    "\n",
    "        # top_sort = []\n",
    "        # print(queue, indegre)\n",
    "        while queue:\n",
    "            if len(queue)>1:\n",
    "                return False\n",
    "            x = queue.popleft()\n",
    "\n",
    "            for nei in graph[x]:\n",
    "                indegre[nei] -= 1\n",
    "                if indegre[nei]==0:\n",
    "                    queue.append(nei)\n",
    "\n",
    "        # print(top_sort)\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "\n",
    "        # 构建图\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                graph[seq[i]].append(seq[i+1])\n",
    "                indegree[seq[i+1]] += 1\n",
    "\n",
    "        # 找出入度为0的节点\n",
    "        queue = deque([node for node in nums if indegree[node] == 0])\n",
    "\n",
    "        # 对比nums的序列与拓扑排序的序列\n",
    "        idx = 0\n",
    "        while queue:\n",
    "            if len(queue) != 1:  # 存在多种可能的拓扑序列\n",
    "                return False\n",
    "            curr = queue.popleft()\n",
    "            if curr != nums[idx]:\n",
    "                return False\n",
    "            idx += 1\n",
    "            for neighbor in graph[curr]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "\n",
    "        return idx == len(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        numsList = [[] for _ in range(len(nums))]\n",
    "        dpList = [0 for _ in range(len(nums))]\n",
    "        for seq in sequences:\n",
    "            for x,y in pairwise(seq):\n",
    "                numsList[x-1].append(y-1)\n",
    "                dpList[y-1] += 1\n",
    "        q = deque([i for i, d in enumerate(dpList) if d == 0])\n",
    "        while len(q)!=0:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            cur = q.popleft()\n",
    "            for num in numsList[cur]:\n",
    "                dpList[num] -= 1\n",
    "                if dpList[num] == 0:\n",
    "                    q.append(num)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        m = len(sequences)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        vit = [0] * n\n",
    "        for i in range(m):\n",
    "            for j in range(len(sequences[i]) - 1):\n",
    "                graph[sequences[i][j] - 1].append(sequences[i][j + 1] - 1)\n",
    "                vit[sequences[i][j + 1] - 1] += 1\n",
    "        #print(vit)\n",
    "        res = [0] * n\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if vit[i - 1] == 0:\n",
    "                q.append(i - 1)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            temp = q.popleft()\n",
    "            for x in graph[temp]:\n",
    "                res[x] = max(res[x], res[temp] + 1)\n",
    "                vit[x] -= 1\n",
    "                if vit[x] == 0:\n",
    "                    q.append(x)\n",
    "        #print(res)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        m = len(sequences)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        vit = [0] * n\n",
    "        for i in range(m):\n",
    "            for j in range(len(sequences[i]) - 1):\n",
    "                if sequences[i][j + 1] - 1 not in graph[sequences[i][j] - 1]:\n",
    "                    graph[sequences[i][j] - 1].append(sequences[i][j + 1] - 1)\n",
    "                    vit[sequences[i][j + 1] - 1] += 1\n",
    "        #print(vit)\n",
    "        res = [0] * n\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if vit[i - 1] == 0:\n",
    "                q.append(i - 1)\n",
    "        while q:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            temp = q.popleft()\n",
    "            for x in graph[temp]:\n",
    "                res[x] = max(res[x], res[temp] + 1)\n",
    "                vit[x] -= 1\n",
    "                if vit[x] == 0:\n",
    "                    q.append(x)\n",
    "        #print(res)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        vis = [False] * (n+1)\n",
    "        indeg = [0] * (n+1)\n",
    "        HashTable = defaultdict(list)\n",
    "        for sublist in sequences:\n",
    "            temp = sublist[0]\n",
    "            vis[temp] = True\n",
    "            for vali in range(1,len(sublist)):\n",
    "                HashTable[temp].append(sublist[vali])\n",
    "                indeg[sublist[vali]] += 1\n",
    "                vis[sublist[vali]] = True\n",
    "                temp = sublist[vali]\n",
    "\n",
    "        if vis[1:] != [True] * n:\n",
    "            return False\n",
    "\n",
    "        tempflag = False\n",
    "        for i in range(1,n+1):\n",
    "            if indeg[i] == 0 and i==nums[0]:\n",
    "                tempflag = True\n",
    "            elif indeg[i] == 0:\n",
    "                return False\n",
    "        if tempflag == False:\n",
    "            return False\n",
    "        flagi = 0\n",
    "        while True:\n",
    "            if flagi == n-1:\n",
    "                if indeg[nums[flagi]] == 0:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if indeg[nums[flagi]] == 0 :\n",
    "                count = 0\n",
    "                for val in HashTable[nums[flagi]]:\n",
    "                    indeg[val] -= 1\n",
    "                    if indeg[val] == 0:\n",
    "                        count += 1\n",
    "                if count != 1 :\n",
    "                    return False\n",
    "                flagi += 1\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        graph = {num:[] for num in range(1,n+1)}\n",
    "        degree = {num:0 for num in range(1,n+1)}\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)-1):\n",
    "                graph[seq[i]].append(seq[i+1])\n",
    "                degree[seq[i+1]] += 1\n",
    "        nextnum = []\n",
    "        for num in degree:\n",
    "            if(degree[num] == 0):\n",
    "                nextnum.append(num)\n",
    "        # if(len(nextnum) > 1):\n",
    "        #     return False\n",
    "        while(len(nextnum) > 0):\n",
    "            if(len(nextnum) > 1):\n",
    "                return False\n",
    "            u = nextnum[0]\n",
    "            nextnum = []\n",
    "            for v in graph[u]:\n",
    "                degree[v] -= 1\n",
    "                if(degree[v] == 0):\n",
    "                    nextnum.append(v)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        graph = {num:[] for num in range(1,n+1)}\n",
    "        degree = {num:0 for num in range(1,n+1)}\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)-1):\n",
    "                graph[seq[i]].append(seq[i+1])\n",
    "                degree[seq[i+1]] += 1\n",
    "        nextnum = []\n",
    "        for num in degree:\n",
    "            if(degree[num] == 0):\n",
    "                nextnum.append(num)\n",
    "        while(len(nextnum) > 0):\n",
    "            if(len(nextnum) > 1):\n",
    "                return False\n",
    "            u = nextnum[0]\n",
    "            nextnum = []\n",
    "            for v in graph[u]:\n",
    "                degree[v] -= 1\n",
    "                if(degree[v] == 0):\n",
    "                    nextnum.append(v)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # 结果其实是有顺序的\n",
    "        # 拓扑排序\n",
    "        edges = defaultdict(list)\n",
    "        degree = defaultdict(int)\n",
    "        se = set()\n",
    "        for i in range(len(sequences)):\n",
    "            if len(sequences[i]) == 1:\n",
    "                se.add(sequences[i][0])\n",
    "                continue\n",
    "            else:\n",
    "                for j in range(len(sequences[i])-1):\n",
    "                    x = sequences[i][j]\n",
    "                    y = sequences[i][j+1]\n",
    "                    degree[y] += 1 #入度加一\n",
    "                    edges[x].append(y)\n",
    "                    se.add(x)\n",
    "                    se.add(y)\n",
    "        queue = collections.deque()\n",
    "        for x in se:\n",
    "            if degree[x] == 0:\n",
    "                queue.append(x)\n",
    "        if len(queue) != 1:#nums 是序列的唯一最短 超序列 \n",
    "            return False\n",
    "        ans = []\n",
    "        while queue:\n",
    "            x = queue.popleft()\n",
    "            ans.append(x)\n",
    "            for y in edges[x]:\n",
    "                degree[y] -= 1\n",
    "                if degree[y] == 0:\n",
    "                    queue.append(y)\n",
    "            if len(queue)>1:\n",
    "                return False\n",
    "        return ans == nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        graph = {num:[] for num in range(1,n+1)}\n",
    "        degree = {num:0 for num in range(1,n+1)}\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)-1):\n",
    "                graph[seq[i]].append(seq[i+1])\n",
    "                degree[seq[i+1]] += 1\n",
    "        nextnum = []\n",
    "        for num in degree:\n",
    "            if(degree[num] == 0):\n",
    "                nextnum.append(num)\n",
    "        while(len(nextnum) > 0):\n",
    "            if(len(nextnum) > 1):\n",
    "                return False\n",
    "            u = nextnum[0]\n",
    "            nextnum = []\n",
    "            for v in graph[u]:\n",
    "                degree[v] -= 1\n",
    "                if(degree[v] == 0):\n",
    "                    nextnum.append(v)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        graph = {num:[] for num in range(1,n+1)}\n",
    "        degree = {num:0 for num in range(1,n+1)}\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)-1):\n",
    "                graph[seq[i]].append(seq[i+1])\n",
    "                degree[seq[i+1]] += 1\n",
    "        nextnum = []\n",
    "        for num in degree:\n",
    "            if(degree[num] == 0):\n",
    "                nextnum.append(num)\n",
    "        while(len(nextnum) > 0):\n",
    "            if(len(nextnum) > 1):\n",
    "                return False\n",
    "            u = nextnum[0]\n",
    "            nextnum = []\n",
    "            for v in graph[u]:\n",
    "                degree[v] -= 1\n",
    "                if(degree[v] == 0):\n",
    "                    nextnum.append(v)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        graph = [set() for i in range(n + 1)]\n",
    "        for seq in sequences:\n",
    "            for a, b in zip(seq, seq[1:]):\n",
    "                graph[a].add(b)\n",
    "        \n",
    "        for i in range(n - 1):\n",
    "            cur = nums[i]\n",
    "            if nums[i + 1] not in graph[cur]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "\n",
    "        # 记录每个数的子结点\n",
    "        d = defaultdict(set)\n",
    "        for seq in sequences:\n",
    "            for i in range(1, len(seq)):\n",
    "                d[seq[i-1]].add(seq[i])\n",
    "\n",
    "      # 检查 nums 是否一条从头到尾的一条路径\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] not in d[nums[i-1]]: \n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # 结果其实是有顺序的\n",
    "        # 拓扑排序\n",
    "        edges = defaultdict(list)\n",
    "        degree = defaultdict(int)\n",
    "        se = set()\n",
    "        for i in range(len(sequences)):\n",
    "            if len(sequences[i]) == 1:\n",
    "                se.add(sequences[i][0])\n",
    "                continue\n",
    "            else:\n",
    "                for j in range(len(sequences[i])-1):\n",
    "                    x = sequences[i][j]\n",
    "                    y = sequences[i][j+1]\n",
    "                    degree[y] += 1\n",
    "                    edges[x].append(y)\n",
    "                    se.add(x)\n",
    "                    se.add(y)\n",
    "        queue = collections.deque()\n",
    "        for x in se:\n",
    "            if degree[x] == 0:\n",
    "                queue.append(x)\n",
    "        if len(queue) != 1:\n",
    "            return False\n",
    "        ans = []\n",
    "        while queue:\n",
    "            x = queue.popleft()\n",
    "            ans.append(x)\n",
    "            for y in edges[x]:\n",
    "                degree[y] -= 1\n",
    "                if degree[y] == 0:\n",
    "                    queue.append(y)\n",
    "            if len(queue)>1:\n",
    "                return False\n",
    "        return ans == nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # 拓扑排序\n",
    "\n",
    "        n = len(nums)\n",
    "        indegree = {idx: 0 for idx in range(1, n + 1)}\n",
    "        connect = {idx: [] for idx in range(1, n + 1)}\n",
    "\n",
    "        for sequence_item in sequences:\n",
    "            for idx in range(len(sequence_item) - 1):\n",
    "                pre, cur = sequence_item[idx], sequence_item[idx + 1]\n",
    "                indegree[cur] += 1\n",
    "                connect[pre].append(cur)\n",
    "        \n",
    "        queue = deque()\n",
    "        for idx in range(1, n + 1):\n",
    "            if indegree[idx] == 0:\n",
    "                queue.append(idx)\n",
    "        \n",
    "        if len(queue) > 1:\n",
    "            return False\n",
    "        \n",
    "        ret_list = []\n",
    "\n",
    "        while queue:\n",
    "            if len(queue) > 1:\n",
    "                return False\n",
    "            item = queue.popleft()\n",
    "            ret_list.append(item)\n",
    "            for next_candidate in connect[item]:\n",
    "                indegree[next_candidate] -= 1\n",
    "                if indegree[next_candidate] == 0:\n",
    "                    queue.append(next_candidate)\n",
    "                \n",
    "\n",
    "        return ret_list == nums\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        l = len(nums)\n",
    "        d = {}\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                if seq[i] not in d:\n",
    "                    d[seq[i]] = set()\n",
    "                d[seq[i]].add(seq[i + 1])\n",
    "        for i in range(l - 1):\n",
    "            if nums[i] not in d or nums[i + 1] not in d[nums[i]]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        indegrees = {idx: 0 for idx in range(1, n + 1)}\n",
    "        adjacency = {idx: [] for idx in range(1, n + 1)}\n",
    "        queue = deque()\n",
    "        # Get the indegree and adjacency of every course.\n",
    "        for seq_item in sequences:\n",
    "            for start_idx in range(0, len(seq_item) - 1):\n",
    "                pre, cur = seq_item[start_idx], seq_item[start_idx + 1]\n",
    "                indegrees[cur] += 1\n",
    "                adjacency[pre].append(cur)\n",
    "        # Get all the courses with the indegree of 0.\n",
    "        for i in indegrees:\n",
    "            if not indegrees[i]: queue.append(i)\n",
    "        # BFS TopSort.\n",
    "        if len(queue) > 1:\n",
    "            return False\n",
    "\n",
    "        ret_list = []\n",
    "        while queue:\n",
    "            if len(queue) > 1:\n",
    "                return False\n",
    "            pre = queue.popleft()\n",
    "            ret_list.append(pre)\n",
    "            for cur in adjacency[pre]:\n",
    "                indegrees[cur] -= 1\n",
    "                if not indegrees[cur]: queue.append(cur)\n",
    "        \n",
    "        return ret_list == nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import copy\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        '''\n",
    "        nums是唯一最短超序列的充要条件就是nums中每一个元素的下一个元素都在哈希表中出现过.  当不在哈希表中出现时,说明此两元素交换位置也可以组成新的超序列,不满足条件\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        rec_dict = {}\n",
    "        for seq in sequences:\n",
    "            en = len(seq)\n",
    "            for i in range(en):\n",
    "                if seq[i] not in rec_dict:\n",
    "                    rec_dict[seq[i]] = set()\n",
    "\n",
    "                if i+1 < en:\n",
    "                    rec_dict[seq[i]].add(seq[i+1])\n",
    "        # print(rec_dict)\n",
    "        for i in range(n-1):\n",
    "            if nums[i] not in rec_dict or nums[i+1] not in rec_dict[nums[i]]:\n",
    "                return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        m = len(sequences)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        vit = [0] * n\n",
    "        for i in range(m):\n",
    "            for j in range(len(sequences[i]) - 1):\n",
    "                if sequences[i][j + 1] - 1 not in graph[sequences[i][j] - 1]:\n",
    "                    graph[sequences[i][j] - 1].append(sequences[i][j + 1] - 1)\n",
    "                    vit[sequences[i][j + 1] - 1] += 1\n",
    "        #print(vit)\n",
    "        res = [0] * n\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if vit[i - 1] == 0:\n",
    "                q.append(i - 1)\n",
    "        while q:\n",
    "            temp = q.popleft()\n",
    "            for x in graph[temp]:\n",
    "                res[x] = max(res[x], res[temp] + 1)\n",
    "                vit[x] -= 1\n",
    "                if vit[x] == 0:\n",
    "                    q.append(x)\n",
    "        #print(res)\n",
    "        if sorted(res) == [i for i in range(n)]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        graph = [set() for _ in range(n + 1)]\n",
    "        in_degree = [0 for _ in range(n + 1)]\n",
    "        for sequence in sequences:\n",
    "            for i in range(len(sequence) - 1):\n",
    "                graph[sequence[i]].add(sequence[i + 1])\n",
    "                in_degree[sequence[i + 1]] += 1\n",
    "        \n",
    "        zero = list()\n",
    "        for i in range(1, n+1):\n",
    "            if in_degree[i] == 0:\n",
    "                zero.append(i)\n",
    "\n",
    "        while zero:\n",
    "            if len(zero) != 1:\n",
    "                return False\n",
    "            cur_root = zero.pop(0)\n",
    "            for next_node in graph[cur_root]:\n",
    "                in_degree[next_node] -= 1\n",
    "                if in_degree[next_node] == 0:\n",
    "                    zero.append(next_node)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        s = set()\n",
    "        for seq in sequences:\n",
    "            for i in seq:\n",
    "                s.add(i)\n",
    "        if len(nums) != len(s):\n",
    "            return False\n",
    "        d = {v: i for i, v in enumerate(list(s))}\n",
    "        n = len(d)\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        degs = [0] * n\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq) - 1):\n",
    "                neighbors[d[seq[i]]].append(d[seq[i + 1]])\n",
    "                degs[d[seq[i + 1]]] += 1\n",
    "        dz = 0\n",
    "        tmp = -1\n",
    "        for i in range(n):\n",
    "            if degs[i] == 0:\n",
    "                dz += 1\n",
    "                tmp = i\n",
    "        if dz != 1:\n",
    "            return False\n",
    "        sq = [tmp]\n",
    "        for _ in range(n - 1):\n",
    "            dz = 0\n",
    "            tmp = -1\n",
    "            for i in neighbors[sq[-1]]:\n",
    "                degs[i] -= 1\n",
    "                if degs[i] == 0:\n",
    "                    dz += 1\n",
    "                    tmp = i\n",
    "            if dz != 1:\n",
    "                return False\n",
    "            sq.append(tmp)\n",
    "        for i in range(n):\n",
    "            if d.get(nums[i], -1) != sq[i]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        l=len(nums)\n",
    "        d={}\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)-1):\n",
    "                if seq[i] not in d:\n",
    "                    d[seq[i]]=set()\n",
    "                d[seq[i]].add(seq[i+1])\n",
    "        #return d\n",
    "\n",
    "        for i in range(l - 1):#检查每个元素是否出现在前一个元素的哈希表值中\n",
    "            if nums[i] not in d or nums[i + 1] not in d[nums[i]]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        g = dict()\n",
    "        n=len(nums)\n",
    "        \n",
    "        for v in sequences:\n",
    "            for i in range(len(v) - 1):\n",
    "                if v[i] not in g:\n",
    "                    g[v[i]] = set()\n",
    "                g[v[i]].add(v[i+1])\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] not in g or nums[i + 1] not in g[nums[i]]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        d = defaultdict(set)\n",
    "        for seq in sequences:\n",
    "            for i in range(1,len(seq)):\n",
    "                d[seq[i-1]].add(seq[i])\n",
    "        \n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] not in d[nums[i-1]]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        adj_dict = defaultdict(list)\n",
    "        elements = set()\n",
    "        in_deg = defaultdict(int)\n",
    "        for sequence in sequences:\n",
    "            if sequence.__len__() == 1:\n",
    "                elements.add(sequence[0])\n",
    "\n",
    "            for i in range(sequence.__len__() - 1):\n",
    "                x, y = sequence[i], sequence[i + 1]\n",
    "                adj_dict[x].append(y)\n",
    "                elements.add(x)\n",
    "                elements.add(y)\n",
    "                in_deg[y] += 1\n",
    "        no_pre = set(elements)\n",
    "\n",
    "        if elements.__len__() != nums.__len__():\n",
    "            return False\n",
    "\n",
    "        for sequence in sequences:\n",
    "            for i in range(sequence.__len__() - 1):\n",
    "                x, y = sequence[i], sequence[i + 1]\n",
    "                try:\n",
    "                    no_pre.remove(y)\n",
    "                except KeyError:\n",
    "                    pass\n",
    "\n",
    "        ptr = 0\n",
    "        while no_pre:\n",
    "            if no_pre.__len__() != 1:\n",
    "                return False\n",
    "            c = no_pre.pop()\n",
    "            if nums[ptr] != c:\n",
    "                return False\n",
    "            ptr += 1\n",
    "            for next_node in adj_dict[c]:\n",
    "                in_deg[next_node] -= 1\n",
    "                if in_deg[next_node] == 0:\n",
    "                    no_pre.add(next_node)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        p = defaultdict(set)\n",
    "        for seq in sequences:\n",
    "            for i in range(1, len(seq)):\n",
    "                p[seq[i-1]].add(seq[i])\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i+1] not in p[nums[i]]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        d={}\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)-1):\n",
    "                if seq[i] not in d:\n",
    "                    d[seq[i]]=set()\n",
    "                d[seq[i]].add(seq[i+1])\n",
    "        \n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] not in d or nums[i+1] not in d[nums[i]]:\n",
    "                return False\n",
    "        return  True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n=len(nums)\n",
    "        in_degrees=[0 for _ in range(n)]\n",
    "        adj=[set() for _ in range(n)]\n",
    "\n",
    "        for sequence in sequences:\n",
    "            for x,y in pairwise(sequence):\n",
    "                adj[x-1].add(y-1)\n",
    "                in_degrees[y-1]+=1\n",
    "\n",
    "        queue=[]\n",
    "\n",
    "        for i in range(n):\n",
    "            if in_degrees[i]==0:\n",
    "                queue.append(i)\n",
    "     \n",
    "        while queue:\n",
    "            if len(queue)>1:\n",
    "                return False\n",
    "            cur=queue.pop(0)\n",
    "\n",
    "            for sub in adj[cur]:\n",
    "                in_degrees[sub]-=1\n",
    "                if in_degrees[sub]==0:\n",
    "                    queue.append(sub)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        dic={}\n",
    "        for sequence in sequences:\n",
    "            for i in range(1,len(sequence)):\n",
    "                if sequence[i-1] not in dic:\n",
    "                    dic[sequence[i-1]]=set()\n",
    "                dic[sequence[i-1]].add(sequence[i])\n",
    "        print(dic)\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i-1] not in dic or nums[i] not in dic[nums[i-1]]:\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        dic = {}\n",
    "        n = len(nums)\n",
    "        count = [0]*(n+1)\n",
    "        for s in sequences:\n",
    "            for i in range(len(s)-1):\n",
    "                a, b = s[i], s[i+1]\n",
    "                if a not in dic:\n",
    "                    dic[a] = {b}\n",
    "                    count[b] += 1\n",
    "                else:\n",
    "                    if b not in dic[a]:\n",
    "                        dic[a].add(b)\n",
    "                        count[b] += 1\n",
    "        # print(dic, count)\n",
    "        queue = [i for i in range(1,n+1) if count[i]==0]\n",
    "        if len(queue)!= 1:\n",
    "            return False\n",
    "        while len(queue)==1:\n",
    "            # print(queue)\n",
    "            x = queue.pop(0)\n",
    "            y = nums.pop(0)\n",
    "            if x!=y:\n",
    "                return False\n",
    "            if x not in dic:\n",
    "                continue\n",
    "            for i in dic[x]:\n",
    "                count[i] -= 1\n",
    "                if count[i] == 0:\n",
    "                    if len(queue)!=0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        queue.append(i)\n",
    "        return nums==[]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        # graph\n",
    "        edges = collections.defaultdict(set)\n",
    "\n",
    "        # indegree\n",
    "        indeg = [0 for _ in nums] + [0]\n",
    "        for seq in sequences:\n",
    "            for i in range(len(seq)-1):\n",
    "                if seq[i+1] not in edges[seq[i]]:\n",
    "                    indeg[seq[i+1]] += 1\n",
    "                    edges[seq[i]].add(seq[i+1])\n",
    "\n",
    "        # queue\n",
    "        q = [i for i in range(1, len(indeg)) if indeg[i] == 0]\n",
    "\n",
    "        while len(q) > 0:\n",
    "            if len(q) > 1:\n",
    "                return False\n",
    "            top = q[0]\n",
    "            q = q[1:]\n",
    "            for nex in edges[top]:\n",
    "                indeg[nex] -= 1\n",
    "                if indeg[nex] == 0:\n",
    "                    q.append(nex)\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = {}\n",
    "        in_degrees = {}\n",
    "        for seq in sequences:\n",
    "            for num in seq:\n",
    "                if num < 1 or num > len(nums):\n",
    "                    return False\n",
    "                if num not in graph:\n",
    "                    graph[num] = set()\n",
    "                if num not in in_degrees:\n",
    "                    in_degrees[num] = 0\n",
    "            for i in range(len(seq)-1):\n",
    "                n1 = seq[i]\n",
    "                n2 = seq[i+1]\n",
    "                if n2 not in graph[n1]:\n",
    "                    graph[n1].add(n2)\n",
    "                    in_degrees[n2] += 1\n",
    "                \n",
    "        q = deque()\n",
    "        for k, v in in_degrees.items():\n",
    "            if v == 0:\n",
    "                q.append(k)\n",
    "        build = []\n",
    "        while len(q) == 1:\n",
    "            num = q.popleft()\n",
    "            build.append(num)\n",
    "            for nxt in graph[num]:\n",
    "                in_degrees[nxt] -= 1\n",
    "                if in_degrees[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        return len(build) == len(nums)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = {}\n",
    "        in_degrees = {}\n",
    "        for seq in sequences:\n",
    "            for num in seq:\n",
    "                # if num > len(nums):\n",
    "                #     return False\n",
    "                if num not in graph:\n",
    "                    graph[num] = set()\n",
    "                if num not in in_degrees:\n",
    "                    in_degrees[num] = 0\n",
    "            for i in range(len(seq)-1):\n",
    "                n1 = seq[i]\n",
    "                n2 = seq[i+1]\n",
    "                if n2 not in graph[n1]:\n",
    "                    graph[n1].add(n2)\n",
    "                    in_degrees[n2] += 1\n",
    "                \n",
    "        q = deque()\n",
    "        for k, v in in_degrees.items():\n",
    "            if v == 0:\n",
    "                q.append(k)\n",
    "        build = []\n",
    "        while len(q) == 1:\n",
    "            num = q.popleft()\n",
    "            build.append(num)\n",
    "            for nxt in graph[num]:\n",
    "                in_degrees[nxt] -= 1\n",
    "                if in_degrees[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        return len(build) == len(nums)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = {}\n",
    "        in_degrees = {}\n",
    "        for seq in sequences:\n",
    "            for num in seq:\n",
    "                if num not in graph:\n",
    "                    graph[num] = set()\n",
    "                if num not in in_degrees:\n",
    "                    in_degrees[num] = 0\n",
    "            for i in range(len(seq)-1):\n",
    "                n1 = seq[i]\n",
    "                n2 = seq[i+1]\n",
    "                if n2 not in graph[n1]:\n",
    "                    graph[n1].add(n2)\n",
    "                    in_degrees[n2] += 1\n",
    "                \n",
    "        q = deque()\n",
    "        for k, v in in_degrees.items():\n",
    "            if v == 0:\n",
    "                q.append(k)\n",
    "        build = []\n",
    "        while len(q) == 1:\n",
    "            num = q.popleft()\n",
    "            build.append(num)\n",
    "            for nxt in graph[num]:\n",
    "                in_degrees[nxt] -= 1\n",
    "                if in_degrees[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        return len(build) == len(nums)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = {}\n",
    "        in_degrees = {}\n",
    "        for seq in sequences:\n",
    "            for num in seq:\n",
    "                if num not in graph:\n",
    "                    graph[num] = set()\n",
    "                if num not in in_degrees:\n",
    "                    in_degrees[num] = 0\n",
    "            for i in range(len(seq)-1):\n",
    "                n1 = seq[i]\n",
    "                n2 = seq[i+1]\n",
    "                if n2 not in graph[n1]:\n",
    "                    graph[n1].add(n2)\n",
    "                    in_degrees[n2] += 1\n",
    "                \n",
    "        q = deque()\n",
    "        for k, v in in_degrees.items():\n",
    "            if v == 0:\n",
    "                q.append(k)\n",
    "        build = []\n",
    "        while len(q) == 1:\n",
    "            num = q.popleft()\n",
    "            build.append(num)\n",
    "            for nxt in graph[num]:\n",
    "                in_degrees[nxt] -= 1\n",
    "                if in_degrees[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        return len(build) == len(nums)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = self.build_graph(sequences)\n",
    "        topo_lst = self.topo_sort(graph)\n",
    "        return nums == topo_lst\n",
    "    \n",
    "    def build_indegree(self, graph):\n",
    "        indegree = {node: 0 for node in graph}\n",
    "        for node in graph:\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] += 1\n",
    "        return indegree\n",
    "\n",
    "\n",
    "    def topo_sort(self, graph):\n",
    "        indegree = self.build_indegree(graph)\n",
    "        queue =  collections.deque([node for node in indegree if indegree[node] == 0])\n",
    "        topo_lst = []\n",
    "        while queue:\n",
    "            if len(queue) > 1: return []\n",
    "            node = queue.popleft()\n",
    "            topo_lst.append(node)\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "\n",
    "        return topo_lst if len(topo_lst) == len(graph) else []\n",
    "\n",
    "        \n",
    "\n",
    "    def build_graph(self, sequences):\n",
    "        graph = {}\n",
    "        for seq in sequences:\n",
    "            for node in seq:\n",
    "                if node not in graph:\n",
    "                    graph[node] = set()\n",
    "\n",
    "        for seq in sequences:\n",
    "            for i in range(1, len(seq)):\n",
    "                graph[seq[i - 1]].add(seq[i])\n",
    "        \n",
    "        return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = self.build_graph(sequences)\n",
    "        topo_lst = self.topo_sort(graph)\n",
    "        return nums == topo_lst\n",
    "    \n",
    "    def build_indegree(self, graph):\n",
    "        indegree = {node: 0 for node in graph}\n",
    "        for node in graph:\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] += 1\n",
    "        return indegree\n",
    "\n",
    "\n",
    "    def topo_sort(self, graph):\n",
    "        indegree = self.build_indegree(graph)\n",
    "        queue =  collections.deque([node for node in indegree if indegree[node] == 0])\n",
    "        topo_lst = []\n",
    "        while queue:\n",
    "            if len(queue) > 1: return []\n",
    "            node = queue.popleft()\n",
    "            topo_lst.append(node)\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "\n",
    "        return topo_lst if len(topo_lst) == len(graph) else []\n",
    "\n",
    "        \n",
    "\n",
    "    def build_graph(self, sequences):\n",
    "        graph = {}\n",
    "        for seq in sequences:\n",
    "            for node in seq:\n",
    "                if node not in graph:\n",
    "                    graph[node] = set()\n",
    "\n",
    "        for seq in sequences:\n",
    "            for i in range(1, len(seq)):\n",
    "                graph[seq[i - 1]].add(seq[i])\n",
    "        \n",
    "        return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        if len(nums)==1:\n",
    "            return True\n",
    "        graph = {}\n",
    "        indegree = {}\n",
    "        for seq in sequences:\n",
    "            for char in seq:\n",
    "                graph[char]=set()\n",
    "                indegree[char] = 0\n",
    "\n",
    "        for seq in sequences:\n",
    "            for idx in range(len(seq)-1):\n",
    "                if seq[idx+1] not in graph[seq[idx]]:\n",
    "                    graph[seq[idx]].add(seq[idx+1])\n",
    "                    indegree[seq[idx+1]]+=1\n",
    "\n",
    "        if len(graph)!=len(nums):\n",
    "            return False      \n",
    "        \n",
    "        \n",
    "        queue = []\n",
    "        res = []\n",
    "        for item in indegree:\n",
    "            if indegree[item]==0:\n",
    "                queue.append(item)\n",
    "        \n",
    "        while queue:\n",
    "            if len(queue)>1:\n",
    "                return False\n",
    "            cur = queue.pop(0)\n",
    "            res.append(cur)\n",
    "            for nxt in graph[cur]:\n",
    "                indegree[nxt]-=1\n",
    "                if indegree[nxt]==0:\n",
    "                    queue.append(nxt)\n",
    "        # print(graph, res)\n",
    "        if res==list(nums):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        n = len(nums)\n",
    "        indegree = [0] * (n + 1)\n",
    "        graph = [{} for _ in range(n + 1)]\n",
    "\n",
    "        # 初始化入度和图\n",
    "        for i in range(1, n + 1):\n",
    "            graph[i] = {}\n",
    "\n",
    "        for seq in sequences:\n",
    "            # 建立拓扑关系（偏序关系）\n",
    "            for i in range(1, len(seq)):\n",
    "                # 如果该依赖关系没有添加过则添加\n",
    "                from_num, to_num = seq[i - 1], seq[i]\n",
    "                if from_num < 1 or from_num > n or to_num < 0 or to_num > n:\n",
    "                    # 出现了不在范围内的字符，不是超序列\n",
    "                    return False\n",
    "                # 建立依赖，统计入度\n",
    "                if to_num not in graph[from_num]:\n",
    "                    graph[from_num][to_num] = {}\n",
    "                    indegree[to_num] += 1\n",
    "\n",
    "        # 拓扑排序\n",
    "        queue = []\n",
    "        for i in range(1, len(indegree)):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "\n",
    "        i = 0\n",
    "        while queue:\n",
    "            if nums[i] != queue[0]:\n",
    "                # 排序不一致\n",
    "                return False\n",
    "\n",
    "            if len(queue) > 1:\n",
    "                # 任何时刻只能有一个入度为0的节点\n",
    "                return False\n",
    "\n",
    "            num = queue[0]\n",
    "            i += 1\n",
    "            queue = queue[1:]\n",
    "            # 减少后置节点入度\n",
    "            for key in graph[num]:\n",
    "                indegree[key] -= 1\n",
    "                if indegree[key] == 0:\n",
    "                    queue.append(key)\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        if not sequences:\n",
    "            return False\n",
    "\n",
    "        graph = {}\n",
    "        for seq in sequences:\n",
    "            for node in seq:\n",
    "                if node not in graph:\n",
    "                    graph[node] = set()\n",
    "\n",
    "        for seq in sequences:\n",
    "            for node1, node2 in pairwise(seq):\n",
    "                graph[node1].add(node2)\n",
    "\n",
    "        indegree = {node: 0 for node in graph}\n",
    "        for node in graph:\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] += 1\n",
    "\n",
    "        queue = deque()\n",
    "        for node in graph:\n",
    "            if indegree[node] == 0:\n",
    "                queue.append(node)\n",
    "\n",
    "        result = []\n",
    "        while queue:\n",
    "            if len(queue) > 1:\n",
    "                return False\n",
    "            node = queue.popleft()\n",
    "            result.append(node)\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "        if len(result) != len(graph):\n",
    "            return False\n",
    "\n",
    "        return result == nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        graph = self.build_graph(sequences)\n",
    "        res = self.topo_sort(graph)\n",
    "        \n",
    "        return res == nums\n",
    "    \n",
    "    def build_indegree(self, graph):\n",
    "        indegree = {node: 0 for node in graph}\n",
    "        for node in graph:\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] += 1\n",
    "        \n",
    "        return indegree\n",
    "\n",
    "    def topo_sort(self, graph):\n",
    "        indegree = self.build_indegree(graph)\n",
    "        queue = collections.deque([node for node in indegree if indegree[node] == 0])\n",
    "        res = []\n",
    "        while queue:\n",
    "            if len(queue) > 1: return []\n",
    "            node = queue.popleft()\n",
    "            res.append(node)\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "\n",
    "        return res if len(res) == len(graph) else []\n",
    "\n",
    "    def build_graph(self, sequences):\n",
    "        graph = {}\n",
    "        for seq in sequences:\n",
    "            for char in seq:\n",
    "                if char not in graph:\n",
    "                    graph[char] = set()\n",
    "        \n",
    "        for seq in sequences:\n",
    "            for i in range(1, len(seq)):\n",
    "                graph[seq[i - 1]].add(seq[i])\n",
    "        \n",
    "        return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        if len(nums)==1:\n",
    "            return True\n",
    "        graph = {}\n",
    "        indegree = {}\n",
    "        for seq in sequences:\n",
    "            for idx in range(len(seq)-1):\n",
    "                if not graph.get(seq[idx]):\n",
    "                    graph[seq[idx]]=set()\n",
    "                if not graph.get(seq[idx+1]):\n",
    "                    graph[seq[idx+1]]=set()\n",
    "                if not indegree.get(seq[idx]):\n",
    "                    indegree[seq[idx]] = 0\n",
    "                if not indegree.get(seq[idx+1]):\n",
    "                    indegree[seq[idx+1]] = 0\n",
    "                if seq[idx+1] not in graph[seq[idx]]:\n",
    "                    indegree[seq[idx+1]]+=1\n",
    "\n",
    "                \n",
    "                graph[seq[idx]].add(seq[idx+1])\n",
    "                \n",
    "        print(graph, indegree)\n",
    "        queue = []\n",
    "        res = []\n",
    "        for item in indegree:\n",
    "            if indegree[item]==0:\n",
    "                queue.append(item)\n",
    "        \n",
    "        while queue:\n",
    "            if len(queue)>1:\n",
    "                return False\n",
    "            cur = queue.pop(0)\n",
    "            res.append(cur)\n",
    "            for nxt in graph[cur]:\n",
    "                indegree[nxt]-=1\n",
    "                if indegree[nxt]==0:\n",
    "                    queue.append(nxt)\n",
    "        # print(graph, res)\n",
    "        if res==list(nums):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:\n",
    "        \"\"\"\n",
    "        因为sequences[i]是nums的子序列。因此，\n",
    "        当\n",
    "            1. sequences形成不含环的有向图\n",
    "            2. 有向图所有节点与nums一致\n",
    "            3. 有向图形成的最长边唯一，且与nums一致\n",
    "        则 nums 是唯一的额最短超序列。\n",
    "        \"\"\"\n",
    "        graph = collections.defaultdict(set)\n",
    "        heads = set()\n",
    "        children = set()\n",
    "\n",
    "        for seq in sequences:\n",
    "            heads.add(seq[0])\n",
    "            for i in range(1, len(seq)):\n",
    "                graph[seq[i-1]].add(seq[i])\n",
    "                children.add(seq[i])\n",
    "\n",
    "        for node in range(1, len(nums)+1):\n",
    "            if node not in heads and node not in children:\n",
    "                return False\n",
    "        \n",
    "        if len(children) != len(nums) - 1:  # 除头节点外，所有节点必须是某个节点的孩子\n",
    "            return False\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] not in graph[nums[i-1]]:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
